package main.回溯;

import java.util.*;

/**
 * @author tmh
 * @date 2024/7/21 20:06
 * @description
 * 有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：
 *
 *     排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
 *     组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。
 *
 * 作者：liweiwei1419
 * 链接：https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class T39组合总和 {
    //result存放结果
    List<List<Integer>> result = new ArrayList<>();
    //数组长度
    int len;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length <= 0) {
            return result;
        }
        len = candidates.length;
        //排序
        Arrays.sort(candidates);
        //list用来存储中间结果
        Deque<Integer> deque =new ArrayDeque<>();
        dfs(candidates, 0, target, deque);
        return result;
    }

    /**
     * 使用begin的作用就是在遍历同一层节点的时候都不在使用candidate里面已经使用过的元素
     *
     * @param candidates
     * @param begin
     * @param target
     * @param deque
     */
    private void dfs(int[] candidates, int begin, int target, Deque<Integer> deque) {
        if (target == 0) {
            //把结果添加进result里面
            result.add(new ArrayList<>(deque));
            return;
        }
        for (int i = begin; i < len; i++) {
            //剪枝
            if (target - candidates[i] < 0) {
                break;
            }
            //添加candidates[i]
            deque.add(candidates[i]);
            dfs(candidates, i, target - candidates[i], deque);
            //把最后添加的元素移除出去
            deque.removeLast();
        }
    }


}
